МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних "БІНАРНЕ ДЕРЕВО ПОШУКУ" МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 7 з дисципліни " Програмування. Частина III. Структури даних та алгоритми " для студентів напряму 6.050102 “Комп’ютерна інженерія” Львів – 2010 Методичні вказівки до лабораторної роботи "Структура даних "БІНАРНЕ ДЕРЕВО ПОШУ-КУ"" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 16 с. Укладач: Лисак Т.А., ст. викладач каф.ЕОМ Відповідальний за випуск: Мельник А.О., д-р техн. наук, проф. Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ Юрчак І.Ю., доцент кафедри САПР, к.т.н.  1. МЕТА РОБОТИ Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам: існує один виокремлений вузол - корень (root) дерева інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1.Tm і кожна з цих множин в свою чергу є деревом. Дерева T1.Tm мають назву піддерев (subtrees) даного кореня.
З цього визначення випливає, що кожна вершина є в свою чергу коренем деякого піддерева. Кількість піддерев вершини має назву ступеня (degree) цієї вершини. Вершина ступеню нуль має назву кінцевої (terminal) або листа (leaf). Некінцева вершина також має назву вершини розгалуження (branch node). Нехай x - довільна вершина дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вершини на цьому шляху називаються предками (ancestors) x; якщо деяка вершина y є предком x, то x називається нащадком (descendant) y. Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками. Кожну вершину x, в свою чергу, можна розглядати як корень деякого піддерево, елементами якого є вершини-нащадки x. Якщо вершини x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називається батьком (parent) до y, а y - сином (child) x. Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings). Вершини, що мають нащадків, називаються внутрішніми (internal). Глибиною вершини x називається довжина шляху від кореня до цієї вершини. Максимальна глибина вершин дерева називається висотою. Якщо існує відносний порядок на піддеревах T1.Tm, то таке дерево називається впорядкованим (ordered tree) або пласким (plane tree). Лісом (forest) називають множину дерев, які не перетинаються. Найчастіше дерева в інформатиці зображують з коренем, який знаходиться зверху (говорять, що дерево в інформатиці "росте вниз"). Важливим окремим випадком кореневих дерев є бінарні дерева, які широко застосовуються в програмуванні і визначаються як множина вершин, яка має виокремлений корінь та два піддерева (праве та ліве), що не перетинаються, або є пустою множиною вершин (на відміну від звичайного дерева, яке не може бути пустим). Важливими операціями на деревах є: обхід вершин в різному порядку перенумерація вершин пошук елемента додавання елемента у визначене місце в дереві видалення елемента видалення цілого фрагмента дерева додавання цілого фрагмента дерева знаходження кореня для будь-якої вершини Найбільшого розповсюдження ці структури даних набули в тих задачах, де необхідне маніпулювання з ієрархічними даними, ефективний пошук в даних, їхнє структуроване зберігання та модифікація. В програмуванні бінарне дерево - дерево, в якому кожна вершина має не більше двох синів. Зазвичай такі сини називаються прав...